/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 
 * 输入：n = 3
 * 
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 
 */

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    const m = n * 2;
    const res = [];
    const path = new Array(m);

    // i：目前填了多少个括号
    // left：左括号个数
    function dfs(i, left) {
        if (i === m) {
            res.push(path.join(""));
            return;
        }

        if (left < n) { // 可以填的左括号
            path[i] = "(";
            dfs(i + 1, left + 1);
        }
        if (i - left < left) { // 还可以继续填右括号
            path[i] = ")";
            dfs(i + 1, left);
        }
    }

    dfs(0, 0);
    return res;
};

/**
 * 
答疑

问：代码是如何保证左右括号都恰好填了 n 个的？

答：

if open < n 限制左括号至多填 n 个，if (i - open < open) 限制右括号至多填 open 个。
由于一共要填 2n 个括号，那么当我们递归到终点时：
1. 如果左括号少于 n 个，那么右括号也会少于 n 个，与 i == m 矛盾，因为每填一个括号 i 都会增加 1。
2. 如果左括号超过 n 个，与 if open < n 矛盾，这行代码限制了左括号至多填 n 个。
3. 所以递归到终点时，左括号恰好填了 n 个，此时右括号填了 2n−n=n 个。

 */
